class Solution {
 public:
  vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    vector<vector<int>> ans;
    vector<int> path;
    backtracking(root, targetSum, ans, path);
    return ans;
  }
  // 同112题三种遍历序都可以，只不过递归签名不同
  void backtracking(TreeNode* root, int targetSum, vector<vector<int>>& ans,
                    vector<int>& path) {
    if (!root) return;
    path.push_back(root->val);

    if (root->left) {
      backtracking(root->left, targetSum - root->val, ans, path);
      path.pop_back();
    }
    if (root->right) {
      backtracking(root->right, targetSum - root->val, ans, path);
      path.pop_back();
    }
    if (!root->left && !root->right && targetSum == root->val) {
      ans.push_back(path);
      return;
    }
  }
};